import java.util.Arrays;

public class NextPermutation {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int reverseStart = len - 1, beforeReverseStart = len - 2;
        while (beforeReverseStart >= 0) {
            if (nums[beforeReverseStart] < nums[reverseStart]) {
                break;
            } else {
                reverseStart--;
                beforeReverseStart--;
            }
        }
        int needToSwap = len - 1;
        while (needToSwap >= beforeReverseStart && beforeReverseStart >= 0) {
            if (nums[needToSwap] > nums[beforeReverseStart]) {
                swap(nums, needToSwap, beforeReverseStart);
                break;
            } else {
                needToSwap--;
            }
        }
        Arrays.sort(nums, reverseStart, len);

    }

    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
